ggt(a,b)|c beweisen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:58 So 06.07.2014 | | Autor: | Skippy05 |
| Aufgabe | Es seien [mm] a,b$\in\IN$ [/mm] und [mm] c$\in\IZ$. [/mm] Zu zeigen:
xa+yb=c
hat genau dann eine Lösung in [mm] $\IZ$( [/mm] d.h.es gibt [mm] u,v$\in\IZ$ [/mm] mit ua+vb=c)
falls gilt
ggT(a,b)|c
(Zu Verwenden: den Satz über den euklidischen Algorithmus:
es gibt [mm] n,m$\in\IZ$ [/mm] mit na+mb=ggT(a,b)) |
Hallo zusammen,
ah ja noch ein Versuch einen Beweis zu schreiben.
Ich Bitte um Korrekturen und Hinweise
Danke!!
[mm] $\Rightarrow$ [/mm] sei (u,v) eine Lösung der Gleichung
i.e. ua+vb=c
ggT(a,b) ist ein Teiler von c ( ggT(a,b)|c geschrieben ),
wenn es eine k [mm] $\in\IZ$ [/mm] so dass c=k*ggT(a,b)
Es existieren (n,m) mit an+bm=ggT(a,b)
Dann ist
c=k*(an+bm)=akn+bkm=a(kn)+b(km)
[mm] $\Leftarrow [/mm] sei (n,m) mit a(kn)+b(km)=k*an+k*bm=k*(an+bm)
Es gilt an+bm=ggT(a,b)
Dann k*(an+bm)=k*ggT(a,b)=c
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:34 So 06.07.2014 | | Autor: | rmix22 |
Dass mit der Voraussetzung, dass der ggt(a,b) ein Teiler von c ist, folgt, dass es mindestens ein ganzzahliges Lösungspaar gibt, kann man sich aus dem, was du geschrieben hast, zusammen klauben.
Die umgekehrte Richtung seh ich aber noch nicht.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:57 So 06.07.2014 | | Autor: | Skippy05 |
Hallo rmix22,
Oh Danke für deine Antwort!
Meinst du sowas?
c=k*ggT(a,b)
[mm] $n_0=kn'$
[/mm]
[mm] $m_0=km'$
[/mm]
Was du aber nicht gesagt hast: bin ich überhaupt auf dem richtigen Weg?
Ich verstehe immer noch nicht so ganz wie ich die umgekehrte Richtung zeigen soll...
Ich habe schon viele Skripts gelesen aber ich weiss nicht wie ich zeigen soll das u, v eine Lösung sind wenn ggT(a,b)|c.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:05 So 06.07.2014 | | Autor: | rmix22 |
Hallo!
> Ich habe schon viele Skripts gelesen aber ich weiss nicht
> wie ich zeigen soll das u, v eine Lösung sind wenn
> ggT(a,b)|c.
Das ist interessant, weil gerade diese Beweisrichtung könnte man mit gutem Willen und bei schlechtem Licht aus dem, was du gepostet hast, herauslesen 
Sei also
[mm] $a\in\IZ,\ [/mm] \ [mm] b\in\IZ,\ [/mm] \ [mm] c\in\IZ$
[/mm]
sowie
${ggt(a,b) | c}$.
Dann existiert (Euler) ein Paar
[mm] $(n,m)\in\IZ$\times\IZ$
[/mm]
mit
${(n*a+m*b)\ |\ c}$
bzw. (jetzt die Teilbarkeit) es existiert auch ein
[mm] ${k\in\IZ}$
[/mm]
mit
${k*(n*a+m*b) = c}$.
Diese Gleichung schreibt sich mit
${u=k*n},\ \ \ \ v=k*m$
als
${u*a+v*b = c}$
und wegen
[mm] $k\in\IZ,\ [/mm] \ [mm] m\in\IZ,\ [/mm] \ [mm] n\in\IZ$
[/mm]
gilt auch
[mm] $u\in\IZ,\ [/mm] \ [mm] v\in\IZ.$
[/mm]
Somit ist mit
$(u, [mm] v)\in\IZ\times\IZ$
[/mm]
ein ganzzahliges Lösungspaar, welches die Gleichung
$x*a+y*b=c$
erfüllt, gefunden!
Und jetzt du!
Sei also
[mm] $a\in\IZ,\ [/mm] \ [mm] b\in\IZ,\ [/mm] \ [mm] c\in\IZ$
[/mm]
und
$(u, [mm] v)\in\IZ\times\IZ$
[/mm]
eine Lösung der Gleichung
$x*a+y*b=c$.
Zeige, dass der $ggT(a,b)$ ein Teiler von $ c $ ist!
Gruß
RMix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:40 Di 08.07.2014 | | Autor: | Skippy05 |
Hallo rmix22,
Oh ich habe mir schon gedacht das ich was falsch mache, aber sowas.... Oh je!
Ok ich versuche es..
Sei [mm] u,v$\in\IZ$ [/mm] eine Lösung mit
ua +vb=c
c|a, und a=c*u
c|b, und b=c*v
c|a-b dann a-b=c*(u-v)=c*k
Sei [mm] n,m$\in\IZ$ [/mm] mit
na+mb=ggT(a,b) dabei gilt a>b, und a= [mm] b*q+r,q$\in\IZ$ [/mm] und r- Rest
ggT(a,b)|a und a=ggT(a,b)*n
ggT(a,b)|b oder
ggT(a,b)|b*q und b=ggT(a,b)*m*q
ggT(a,b)|a-b*q und a-b*q=ggT(a,b)*n-ggT(a,b)*m*q=ggT(a,b)*(m-n*q)
Kannst du mir bitte sagen ob ich überhaupt richtig vorgehe?
Danke!!!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:12 Di 08.07.2014 | | Autor: | rmix22 |
> Hallo rmix22,
>
> Oh ich habe mir schon gedacht das ich was falsch mache,
> aber sowas.... Oh je!
???
> Ok ich versuche es..
> Sei u,v[mm]\in\IZ[/mm] eine Lösung mit
> ua +vb=c
> c|a, und a=c*u
Und das folgerst du woraus?
Alles was du weisst ist, dass alle beteiligten Variablen ganzzahlig sind und die Gleichung erfüllt ist. Mehr darfst du nicht verwenden/voraussetzen.
Nenn doch den ggt(a,b) der einfacheren Schreibweise wegen vorübergehend T, drücke a und b damit aus und setze in die Gleichung ein.
Gruß RMix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:47 Di 08.07.2014 | | Autor: | Skippy05 |
Hallo rmix22,
Zu deinen "Drei Frage Zeichen"...
Ich verstehe nicht immer was und in welche Richtung ich beweisen muss. Ich habe das Gefühl, ich drehe mich immer im Kreis
oder auf einer Stelle. Obwohl ich die Sätze kenne, kann ich diese praktisch nicht anwenden.
So und jetzt wenn ich dich richtig verstanden habe:
c=ua+vb
c|a--> a=c*u
c|b-->b=c*v
g=ggT(a,b)
na+mb=g --> n*(c*u)+m*(c*v)=g --> c(nu+mv)=g
Vielen Dank für deine Hilfe!!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:07 Di 08.07.2014 | | Autor: | rmix22 |
> Hallo rmix22,
>
> Zu deinen "Drei Frage Zeichen"...
> Ich verstehe nicht immer was und in welche Richtung ich
> beweisen muss. Ich habe das Gefühl, ich drehe mich immer
> im Kreis
> oder auf einer Stelle. Obwohl ich die Sätze kenne, kann
> ich diese praktisch nicht anwenden.
>
>
>
> So und jetzt wenn ich dich richtig verstanden habe:
> c=ua+vb
> c|a--> a=c*u
NEIN!
> c|b-->b=c*v
NEIN!
Warum sollte das gelten? Wie begründest du das?
Setzen wir einmal Zahlen ein:
c = u*a + v*b
11=3*2+1*5
Nach deinem Statement oben wäre nun etwa 11 ein Teiler von 5 und es wäre 2=11*3 (a=c*u). Meinst du das im Ernst?
Das hat doch nichts damit zu tun, dass du beim Beweisen die Richtung aus den Augen verlierst oder Sätze nicht anwenden kannst - das ist einfach nur falsch.
> g=ggT(a,b)
> na+mb=g --> n*(c*u)+m*(c*v)=g --> c(nu+mv)=g
Nein, weil zB a eben nicht c*u ist.
g ist also ein Teiler von a und auch ein Teiler von b (wir benötigen hier gar nicht die Information, dass es der größtmögliche ist). Wie kannst du jetzt a und b mithilfe von g ausdrücken?
Gruß RMix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:03 Mi 09.07.2014 | | Autor: | Skippy05 |
Hallo,
Also ich möchte erstmal aufschreiben was ich am Anfang dachte.
ich glaube ich weiss wo ich falsch "abgebogen habe"
Also ggT=g mit na+mb=g
g|a, und g|b, dh g|na und g|mb
Und dann habe ich noch die Gleichung ua+vb=c
Da g|na und g|mb dann teilt es auch g|ua und g|vb
Also dann auch g|c
Ich weiss das ist eine sehr primitive Erklärung...ich hoffe man kann das auch verstehen
Ich kann das auch versuchen mit dem Beispiel zu erklären. .
ggT(8,5)=1
und die Gleichung sieht so aus:
1=2*8+(-3)*5 dabei g=1, a=8 und b=5
Dabei a und b sind konstant, was sich ändert sind Koeffizienten.
Meinst du das gleiche oder was anderes mit a und b durch g ausdrücken?
Ich verstehe dein Beispiel nicht, mit 11=3*2+8*5
Kannst du mir ein anderes zeigen?
Vielen Dank!!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:45 Mi 09.07.2014 | | Autor: | rmix22 |
Hallo,
> Also ich möchte erstmal aufschreiben was ich am Anfang
> dachte.
> ich glaube ich weiss wo ich falsch "abgebogen habe"
>
> Also ggT=g mit na+mb=g
Du brauchst den Euklid für diese Beweisrichtung nicht
> g|a, und g|b, dh g|na und g|mb
Die ersten beiden aussagen sind die relevanten.
> Und dann habe ich noch die Gleichung ua+vb=c
> Da g|na und g|mb dann teilt es auch g|ua und g|vb
Das ist ein falscher Schluß. Nur weil eine Zahl ein Teiler von n*a ist, ist sie deswegen noch lang kein Teiler von u*a!
Aber zum Glück haben wir ja auch g|a und daraus folgt tatsächlich g|u*a und somit kann der Beweis geführt werden. Was bei dir durchgehend fehlt ist die Angabe, dass die beteiligten Größen ganzzahlig sind.
> Meinst du das gleiche oder was anderes mit a und b durch g
> ausdrücken?
Ein wenig:
[mm] $g|a\Rightarrow\exists{m\in\IZ}\text{ mit }a=m*g$
[/mm]
[mm] $g|b\Rightarrow\exists{n\in\IZ}\text{ mit }b=n*g$
[/mm]
Damit wird die Gleichung
$u*a+v*b=c$
zu
$u*m*g+v*n*g=c$
$g*(u*m+v*n)=c$
[mm] $(u*m+v*n)\in\IZ\Rightarrow{g|c}$
[/mm]
>
> Ich verstehe dein Beispiel nicht, mit 11=3*2+8*5
> Kannst du mir ein anderes zeigen?
Wozu? Du hattest die Behauptung aufgestellt, dass aus der Existenz der Gleichung
$c=u*a+v*b$ (alle beteiligten Variablen ganzzahlig)
unter anderem die Beziehungen folgen
$c|b$
und
$a=c*u$
was Unfug ist.
Um dir das zu demonstrieren habe ich beliebige Zahlen eingesetzt
$a=2, b=5, u=3 [mm] \text{ und }v=1$
[/mm]
womit sich $c=11$ ergibt, damit die Angabegleichung erfüllt ist.
Jetzt setze selbst diese Zahlen in die von dir behaupteten Beziehungen ein, dann siehst du hoffentlich, dass diese allesamt nicht richtig sind.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:12 Mi 09.07.2014 | | Autor: | Skippy05 |
Hallo rmix22,
Danke erstmal für deine Erklärungen!
> > g|a, und g|b, dh g|na und g|mb
> Die ersten beiden aussagen sind die relevanten.
>
> > Und dann habe ich noch die Gleichung ua+vb=c
> > Da g|na und g|mb dann teilt es auch g|ua und g|vb
> Das ist ein falscher Schluß. Nur weil eine Zahl ein
> Teiler von n*a ist, ist sie deswegen noch lang kein Teiler
> von u*a!
Ich dachte das wenn g|a dann ist g|na und g|ua, weil n und u sind Koeffizienten, und n und u stellen nur das Vielfache von a dar.
Ich irre mich vielleicht aber ich habe sowas in Zahlentheorie gelesen.
Oder weisst du einen Beispiel , das es widerlegt?
> Aber zum Glück haben wir ja auch g|a und daraus folgt
> tatsächlich g|u*a und somit kann der Beweis geführt
> werden. Was bei dir durchgehend fehlt ist die Angabe, dass
> die beteiligten Größen ganzzahlig sind.
>
> > Meinst du das gleiche oder was anderes mit a und b durch g
> > ausdrücken?
> Ein wenig:
> [mm]g|a\Rightarrow\exists{m\in\IZ}\text{ mit }a=m*g[/mm]
>
> [mm]g|b\Rightarrow\exists{n\in\IZ}\text{ mit }b=n*g[/mm]
> Damit wird
> die Gleichung
> [mm]u*a+v*b=c[/mm]
> zu
> [mm]u*m*g+v*n*g=c[/mm]
> [mm]g*(u*m+v*n)=c[/mm]
>
> [mm](u*m+v*n)\in\IZ\Rightarrow{g|c}[/mm]
Ah stimmt
> > Ich verstehe dein Beispiel nicht, mit 11=3*2+8*5
> > Kannst du mir ein anderes zeigen?
> Wozu? Du hattest die Behauptung aufgestellt, dass aus der
> Existenz der Gleichung
> [mm]c=u*a+v*b[/mm] (alle beteiligten Variablen ganzzahlig)
> unter anderem die Beziehungen folgen
> [mm]c|b[/mm]
> und
> [mm]a=c*u[/mm]
> was Unfug ist.
> Um dir das zu demonstrieren habe ich beliebige Zahlen
> eingesetzt
> [mm]a=2, b=5, u=3 \text{ und }v=1[/mm]
> womit sich [mm]c=11[/mm] ergibt,
> damit die Angabegleichung erfüllt ist.
> Jetzt setze selbst diese Zahlen in die von dir behaupteten
> Beziehungen ein, dann siehst du hoffentlich, dass diese
> allesamt nicht richtig sind.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:20 Mi 09.07.2014 | | Autor: | rmix22 |
Hallo!
> > > Und dann habe ich noch die Gleichung ua+vb=c
> > > Da g|na und g|mb dann teilt es auch g|ua und g|vb
> > Das ist ein falscher Schluß. Nur weil eine Zahl ein
> > Teiler von n*a ist, ist sie deswegen noch lang kein Teiler
> > von u*a!
>
> Ich dachte das wenn g|a dann ist g|na und g|ua, weil n und
> u sind Koeffizienten, und n und u stellen nur das Vielfache
> von a dar.
n und u stellen nicht das Vielfache von a dar. Es sind ganzzahlige Faktoren und daher stellt deren Produkt mit a jeweils ein (und nicht das) ganzzahliges Vielfaches von a dar.
> Ich irre mich vielleicht aber ich habe sowas in
> Zahlentheorie gelesen.
Das stimmt ja trivialerweise und ich habe es auch bei meinem Beweis verwendet, wie du sehen konntest. Aber du bist ja in deinem Posting von einer völlig anderen Voraussetzung ausgegangen - siehe oben in blau!
Du hast gefolgert, wenn g|(n*a) dann gilt auch g|(u*a).
Und dazu werden dir sicher auch selbst genug Gegenbeispiele einfallen.
Falls nicht: 6|(9*4) aber deswegen gilt sicher nicht 6|(5*4), oder?
Gruß RMix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:24 Do 10.07.2014 | | Autor: | Skippy05 |
Ach ja stimmt . Danke sehr!
|
|
|
|
